// 第3章
// 线性结构
// 在学习排序算法的过程中，我们隐约觉得凭借外部的一些结构可以提升性能，比如堆排序使用了堆，计数排序使用了桶（桶可以看作一个结构体，桶的编号就是它的索引）。

// 接下来，我们将要学习查找算法、搜索算法与匹配算法。它们都非常依赖于某种结构体，因此我们需要先学习一些数据结构。

// C语言中有结构体这个数据结构，而在JavaScript中，我们已经有熟悉的数组与对象了。

// 其实JavaScript数组是一个集数组、栈、队列与散列于一身的结构体，而对象则是一个散列。

// 数据结构分类是比较少的，高手们基本上将这几种数据结构玩得出神入化，本书将带你学习更多有用的数据结构。每种数据结构都有其适用的场合，前辈们发明了它们自有他们的道理。


// 3.1　数据结构的分类
// 数据结构主要分为逻辑结构与存储结构这两类

// 逻辑结构可以简单地理解为数据之间的逻辑关系

// 存储结构，又叫物理结构，指的是数据在物理存储空间上是选择集中存储还是分散存储。如果选择集中存储，就使用顺序存储结构；反之，就使用链式存储结构。
// 至于如何选择，主要取决于存储设备的状态以及数据的用途。
// 由于存储结构太过底层，本章只讲逻辑结构的线性结构。
// 所谓线性结构，就是指它的元素之间存在一对一的关系。一对多就是树，多对多就是图。根据构造方式，逻
// 辑结构的线性结构又细分为许多种：数组、链表、栈、队列、散列、位图、块状链表……

// 3.2　数组
// 数组是应用最广泛的数据结构，被内置到大多数语言当中。
// 数组是在内存中开辟的一段连续空间，并在此空间内存放元素。

// 在静态语言中，数组存在上界、下界的概念，比如一个长度为7的数组，array[0]就是它的上界，array[6]就是它的下界，超出这个范围使用数组就会报出越界错误。

// 但这在JavaScript中是没有问题的，只会返回undefined。这是因为数组又分为静态数组与动态数组。
// 静态数组的大小必须在编译时确认，动态数组允许在运行时申请数组内存。

// JavaScript数组是动态数组，能够自由扩展长度；

// 在C语言中，可以通过malloc来分配动态数组；在C++中，使用new来分配动态数组。
// 另外，C++的标准模板库还提供了动态数组类型vector以及内置的固定数组类型array。

// 数组通常包含如下操作：
// 初始化：let array = []; let b = new Array(4)；
// 添加新元素：push；
// 插入新元素：splice（其他语言一般叫insert）；
// 删除元素：splice（其他语言一般叫remove）；
// 判定数组为空：array.length === 0（其他语言会弄一个isEmpty方法）；
// 排序：sort；
// 倒序：reverse；
// 是否包含某个元素：indexOf/includes/find。

// 如果数组中存在名为length的固有属性，我们就不需要像其他语言那样通过size来获取数组长度了。
// 再说一下数组元素的添加与读取。在添加一个元素时有内置方法会很方便.

// 但如果元素是在中间或前面插入的，那么后面的所有元素都要后挪一位，这会降低性能。
// 删除靠前面的元素也一样，后面的元素都要向前挪一位。

// 读取一个元素时，如果知道它的索引值，那么找到它是极快的，能一步到位。


// 3.3　链表
// 链表是与数组并列的一种底层结构。
// 在我看来，它就是一个个连接起来的对象，每个对象都有一个next属性指向下一个对象。
// 从内存来看，它是不连续分布的。JavaScript没有内置这种数据结构，可能觉得太简单了。

// 链表也分许多种，它本身是复合结构，最基本的单位是结点。

// 结点至少有两个属性，一个用来存放数据，一个用来指向下一个引用

// 对于链表中的每个结点，可以用如下代码实现：
class Node{
  constructor(data){
    this.data = data;
    this.next = null;
  }
}
// 为了方便使用，我们通常会为链表添加几个与数组等效的方法与属性，用于增删改查。


3.3.1　单向链表
// 后面的人会拉着前面人的衣服（next）

// 单向链表通常包含如下操作：
// head：插入结点的起点。
// insertAt(index, data)：插入一个结点。
// removeAt(index, data)：移除一个结点。
// findIndex(index)：寻找一个结点。
// forEach(cb)：遍历所有结点。
// size：返回长度。
// isEmpty：判定是否为空。
// clear：清空所有数据。
// 单向链表的实现代码如下：
class List {
  constructor() {
    this.head = null;
    this.length = 0;
  }
  size() {
    return this.length;
  }
  clear() {
    this.head = null;
    this.length = 0;
  }
  forEach(cb) {
    let node = this.head;
    let i = 0;
    while (node) {
      cb(node.data, i);
      node = node.next;
      i++;
    }
  }
  findIndex(index) {
    let node = this.head;
    let i = 0;
    while (node) {
      if (index === i) {
        return node;
      }
      node = node.next;
      i++;
    }
    return null;
  }
  insertAt(index, value) {
    if (index <= this.length) {
      let node = new Node(value);
      if (index === 0 && !this.head) {
        let temp = this.head;
        this.head = node;
        this.head.next = temp;
      } else {
        let prev = this.findIndex(index - 1);
        let next = prev.next;
        prev.next = node;// A连接B 
        node.next = next;// B连接A 
      }
      this.length++;
    } else {
      throw `${index}超出链表长度${this.length}`;
    }
  }
  removeAt(index) {// 链表内必须有结点
    if (this.head && index <= this.length) {
      let prev = this.findIndex(index - 1);
      let curr = this.findIndex(index);
      if (!prev) { // 前面的结点不存在，说明移除了第一个，那么将后面的放到head
        this.head = curr.next;
      } else {
        prev.next = curr.next;
      }
      this.length--;
    } else {
      throw `${index}超出链表长度${this.length}`;
    }
  }
}
let list = new List();
list.insertAt(0, 111);
list.insertAt(1, 222);
list.insertAt(1, 333);
list.insertAt(3, 444);
list.forEach(function(el, i) {
  console.log(el, i);
});
try {
  list.insertAt(8, 333);
} catch (e) {
  console.log(e);
}
list.removeAt(1);
list.forEach(function(el, i) {
  console.log(el, i);
});

// 我们与数组比较一下，由于链表没有索引这种一步到位的“神器”，要访问某个元素都需要遍历，所以其最坏的情况算是O(n)。

// 但增删元素比数组方便多了，不需要整体后挪，其时间复杂度是O(1)。

// 上面的这种数组叫单向链表，它只能从一个方向开始遍历，即便我们知道这个链表的长度为1000，要访问其第1000个元素，依旧要遍历所有的元素。

// 为了改进这种效率，前辈们发明了双向链表。


// 3.3.2　双向链表

// 双向链表的每个结点比单向链表多了一个属性prev，链表本身也多一个属性tail。

// 每次增删结点时，我们尝试调用一个更快的findIndex方法，
// 它会根据传入的索引值决定从头还是从尾开始查找。

// 双向链表想象几个人站成一排，但不是手拉手，左边的人用右手（next）扯着右边的人的衣角，右边的人用左手（prev）扯着左边的人的衣角。如果中间插入一个，也要断开重连，这时就涉及4个属性的修改。


// 双向链表的实现代码如下：

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}
class DoubleList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  size() {
    return this.length;
  }
  clear() {
    this.constructor();
  }
  findIndex(index) {
    let n = this.length;
    if (index > n) {
      throw `${index}超出链表长度${this.length}`;
    }
    // 判定查找方向
    let dir = index > (n >> 1);
    let node = dir ? this.tail : this.head;
    let prop = dir ? "prev" : "next";
    let add = dir ? -1 : 1;
    let i = dir ? n-1 : 0;
    while (node) {
      if (index === i) {
        return node;
      }
      node = node[prop];
      i = i + add;
    }
    return null;
  }
  forEach(cb) {/**略**/ }
  insertAt(index, value) {
    if (index <= this.length) {
      let node = new Node(value);
      if (index === 0 && !this.head) {
        this.tail = this.head = node;
      } else {
        let prev = this.findIndex(index - 1);
        let next = prev.next;// 这里可能为null
        prev.next = node;// A连B
        node.prev = prev;// B连A
        node.next = next;// B连C
        if (next) {// C连接B
          next.prev = node; // fix
        }
      }
      if (index == this.length) { // fix
        this.tail = node;
      }
      this.length++;
    } else {
      throw `${index}超出链表长度${this.length}`;
    }
  }
  removeAt(index) {
    if (this.head && index <= this.length) {
      let prev = this.findIndex(index - 1);
      let curr = this.findIndex(index),
        next;
      if (!prev) { // 前面的结点不存在，说明移除了第一个，那么将后面的放到head
        next = this.head = curr.next;
      } else {
        next = prev.next = curr.next;
      }
      if (next) { // 如果没有到末端，需要修正后面结点的prev属性
        next.prev = prev;
      } else {
        this.tail = next;// 修正末端
      }
      this.length--;
    } else {
      throw `${index}超出链表长度${this.length}`;
    }
  }
}
let list = new DoubleList();
list.insertAt(0, 111);
list.insertAt(1, 222);
list.insertAt(1, 333);
list.insertAt(3, 444);
list.insertAt(4, 555);
list.insertAt(5, 666);
list.forEach(function(el, i) {
  console.log(el, i);
});
try {
  list.insert(8, 333);
} catch (e) {
  console.log(e);
}
list.removeAt(1);
list.forEach(function(el, i) {
  console.log(el, i);
});



// 3.3.3　有序链表

// 有序链表与上文的两种链表相比，就是在插入结点时，保证数据是有序的。
// 之前已经提过数组在中间插入、移除数据时，其中一侧的数据都需要向前或向后挪动，链表就没有这样的烦恼。

// 有序链表的许多功能与单向链表或双向链表一致，我们没有必要再写一次，直接用类继承进行复用。
// 我们在原类上添加3个方法：find、insert和value。

// 其中find方法编写时需要一些技巧，因为插入时，我们只能插入到比目标值大的结点前，不能使用等于号，而在移除时，
// 我们又想准确删除data等于value的结点，因此设置了第2个参数useByInsert进行区分。但为了防止用户误传一个参数，我们可以传入一个对象进行比较。

// 示例代码如下：
let useByInsert = {};
class SortedList extends DoubleList {
  find(value, second) {// useByInsert为内部对象，外部用户访问不到
    let node = this.head;
    let i = 0;
    while (node) {
      if (second === useByInsert ? node.data > value : node.data === value) {
        return node;
      }
      node = node.next;
      i++;
    }
  }
  insert(value) {
    let next = this.find(value, useByInsert);
    let node = new Node(value);
    if (!next) {
      let last = this.tail;
      // 如果没有结点比它大，它就是tail
      this.tail = node;
      if (last) { // append
        last.next = node;
        node.prev = last;
      } else {
        // 如果什么也没有，它是head
        this.head = node;
      }
    } else {
      let prev = next.prev;
      if (!prev) {
        this.head = node;
        this.head.next = next;
      } else {
        prev.next = node;
        node.next = next;
      }
      node.next = next;
      next.prev = node;
    }
    this.length++;
  }
  remove(value) {
    let node = this.find(value);
    if (node) {
      let prev = node.prev,
        next;
      if (!prev) { // 前面的结点不存在，说明移除了第一个，那么将后面的放到head
        next = this.head = node.next;
      } else {
        next = prev.next = node.next;
      }
      if (next) { // 如果没有到末端，需要修正后面结点的prev属性
        next.prev = prev;
      } else {
        this.tail = next;
      }
      this.length--;
      return true;
    }
    return false;
  }
}

let list = new SortedList();
list.insert(111);
list.insert(222);
list.insert(333);
list.insert(222);
list.insert(444);
list.insert(777);
list.insert(666);
list.forEach(function(el, i) {
  console.log(el, i);
});
console.log(list.size());
try {
  list.insert(333);
} catch (e) {
  console.log(e);
}

list.remove(111);
list.insert(334);
list.remove(777);
list.remove(333);

list.forEach(function(el, i) {
  console.log(el, i);
});


// 3.3.4　双向循环链表
// 面试题——约瑟夫问题，会用到这种数据结构。

// 我们先看一下约瑟夫问题。在罗马人占领乔塔帕特后，39个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。首先从一个人开始，越过k2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
// 我们这个规则是这么定的：在一间房间总共有n个人（下标0～n-1），只能有最后一个人活命。
// 按照如下规则去杀人。
// (1)	所有人围成一圈。
// (2)	顺时针报数，每次报到q的人将被杀掉。
// (3)	被杀掉的人将从房间内被移走。
// (4)	从被杀掉人的下一个人开始重新报数，继续报到q，再清除，直到剩余一人。

// 你要做的是：当你在这一群人之间时，必须选择一个位置以使你变成剩余的最后一人，也就是活下来。
// 这看起来好难，但有了循环链表，就好解决了。循环链表与双向链表的差异不大。
// 首先，双向链表的head与tail是不同的结点，而循环链表的这两个东西都指向一处。
// 既然指向一处，我们就不需要两个属性，只保持一个head就足够了。
// 其次，forEach与find方法需要做一下处理，防止无限循环。
// 因为只有一个结点的循环链表，它的next和prev都是指向自己。所描述的结构如图3-8所示。 

// 双向链表与循环链表的forEach方法如下：

forEach(cb) {// 双向链表
  let node = this.head;
  node = head;
  let i = 0;
  while (node) {
    cb(node.data, i);
    node = node.next;
    i++;
  }
}
forEach(cb) {// 循环链表
  let node = this.head;
  let first = head;
  let i = 0;
  while (node) {
    cb(node.data, i);
    node = node.next;
    if(node === first){
      break; // 循环完成
    }
    i++;
  }
}

// 我们模仿有序链表，让它继承双向链表，然后重写forEach、findIndex、insertAt与removeAt方法：

class CircularLink extends DoubleList {
  forEach(cb) {
    let node = this.head;
    let first = node;
    let i = 0;
    while (node) {
      cb(node.data, i);
      node = node.next;
      if (node === first) {
        break;
      }
      i++;
    }
  }
  findIndex(index) {
    let n = this.length;
    if (index > n) {
      return;
    }
    // 判定查找方向
    let dir = index > (n >> 1);
    let node = this.head;
    let first = node;
    let prop = dir ? "prev" : "next";
    let add = dir ? -1 : 1;
    let i = dir ? n - 1 : 0;
    while (node) {
      if (index === i) {
        return node;
      }
      node = node[prop];
      if (node === first) {
        return node;
      }
      i = i + add;
    }
    return null;
  }
  insertAt(index, value) {
    if (index <= this.length) {
      let node = new Node(value);

      if (index === 0 && !this.head) {
        this.head = node;
        node.prev = node;
        node.next = node;
      } else {
        let prev = this.findIndex(index - 1);
        let next = prev.next; 
        
        prev.next = node;
        node.prev = prev;
        node.next = next;
        next.prev = node; 

      }

      this.length++;
    } else {
      throw `${index}超出链表长度${this.length}`;
    }
  }
  removeAt(index) {
    let node = this.findIndex(index);
    if (node) {
      if (node.next === node) {
        this.head = null;
      } else {
        let prev = node.prev;
        let next = node.next;
        prev.next = next;
        next.prev = prev;
        
        if (node === this.head) {// 如果是，则删掉第一个
          this.head = next;
        }
      }
      this.length--;
      return true;
    }
    return false;
  }
}

let list = new CircularLink();
list.insertAt(0, 111);
list.insertAt(1, 222);
list.insertAt(2, 333);
list.insertAt(1, 444);
list.insertAt(3, 666);

list.forEach(function(el, i) {
  console.log(el, i);
});
list.removeAt(0);
console.log(list);


// 现在让我们解决约瑟夫问题。其实，我们不需要调用循环链表的任何方法，但在学习编写它的方法时，
// 我们熟悉了如何交换next、prev、link.head、link.tail这些属性，这才是真正有用的知识。
// 方法只是方便复用。约瑟夫问题的主要思路是来自forEach与remove方法。
// 我们先建立一个循环链表与一个不断递归调用的kill方法，kill方法在只剩下一个人时停止
// 。如何判定只有一个人，这可以用node.next === node或link.length === 1。kill方法的代码如下：
function kill(list, node, m) {
  let i = 0;
  while (node.next) {
    if (i === m) {
      if (node.next === node) {
        console.log("只剩最后一个了", node.data);
        return true;
      }
      let prev = node.prev;
      let next = node.next;
  
      prev.next = next;
      next.prev = prev;
      list.length--;
      if (node === list.head) {
        list.head = next;
      }
      console.log("移除", node.data);
      break;
    }
    i++;
    node = node.next;
  }
  kill(list, node, m);
}
  
function josephus(n, m) {
  let list = new CircularLink();
  for (let i = 0; i < n; i++) {
    list.insertAt(i, i);
  }
  kill(list, list.head, m);
}
josephus(40,3);


// 3.3.5　链表排序

// 排序时，我们不能使用任何访问link[index]的排序算法，因此有如下排序方法入围。

// 1. 插入排序
// 将链表分为两部分，有序与未排序，每次从未排序区取得第一个结点，在有序区中找到适合的位置进行插入。示例代码如下：

function insertSort(list) {
  let head = list.head;
  // 如果没有或只有一个结点，直接返回
  if (!head || !head.next){
    return;
  } 
  let lastSorted = head;// 排好序的最后一个
  while (lastSorted.next) {// 如果还有下一个
    let firstUnsort = lastSorted.next;// 没有排好序的
    if (lastSorted.val > firstUnsort.val) {
      // 排好序的最前一个
      let firstSorted = head, prev = null;
      // 将firstUnsort移除出来
      lastSorted.next = firstUnsort.next;
      // 求出firstUnsort的插入位置, 让它在有序区中逐一比较
      while (firstSorted.val < firstUnsort.val) {
        prev = firstSorted;
        firstSorted = firstSorted.next;
      }
      if (!prev) {// 如果firstUnsort是最小，那么prev为null
        // 它将成为新的head, 并且旧的head充当它的next
        firstUnsort.next = head;
        head = firstUnsort;
      } else {
        prev.next = firstUnsort;
        firstUnsort.next = firstSorted;
      }
    } else {
      // firstUnsort刚好比lastSorted大
      lastSorted = lastSorted.next;
    }
  }
   // 修正首尾结点
  list.head = head;
  list.tail = lastSorted;
}

let list = new List();
let array = [2, 3, 8, 7, 4, 5, 9, 6, 1, 0];
array.forEach(function(el, i) {
  list.insertAt(i, el);
});
list.forEach(function(el, i) {
  console.log(i, el);
});
insertSort(list);
console.log("----sorted----", list);
list.forEach(function(el, i) {
  console.log(i, el);
});


// 2. 冒泡排序
// 左右结点进行比较交换，并且记录最后的结点，缩小比较的范围。相关代码如下：
function bubbleSort (list) {
  let head = list.head;
  if (!head || !head.next) { // 只有一个或0个结点，不用排序
    return;
  }
  let smallest = new Node(Number.MIN_VALUE);
  smallest.next = head;
  list.tail = null; // 准备重置tail
  let len = 0,  h = smallest;
  while(h){
    len++;
    h = h.next;
  }
  for (let i = 0; i < len; i++) {// 优化1
    let hasSort = true;
    h = smallest;
    p1 = h.next;
    p2 = p1.next;
    for (let j = 0; j < len && p2; j++) {// 优化2
      if (p1.data > p2.data) {
        h.next = p2;
        p1.next = p2.next;
        p2.next = p1;
        hasSort = false;
      }
      h = h.next;
      p1 = h.next;
      p2 = p1.next;
    }
    // 第一次冒泡排序结束后，p1的数据域最大，即为tail（p2已是null）
    if (!list.tail) { 
      list.tail = p1;
    }
    if (hasSort) {
      break;
    }
  }
  // 重置新的head
  list.head = smallest.next;
}

// 回顾之前学到的冒泡排序的优化方法，我们可以减少循环次数，如在“优化1”处，将i = 0改成i = 1；
// 在“优化2”处，则可以将j < len && p2 改成j < len - 1。我
// 们还可以继续优化，引入swapPos变量，减少内循环次数。相关代码如下：
function bubbleSort (list) {
  // 冒泡排序（如果忘记了，可以重新阅读2.1节）
  let k = len - 1,swapPos = 0;
  for (let i = 1; i < len; i++) {
    // 从左边第二个位置开始遍历
    for (let j = 0; j < k; j++) {// k是可变的
      if (p1.data > p2.data) {
        // 判断 p1的数据是否大于p2的数据
        hasSort = false;
        swapPos = j;
      }
    }
    k = swapPos;
  }
  // 重置新的head
  list.head = smallest.next;
}



// 3. 选择排序
// 与插入排序一样，分为两个区，但它是每次从无序区找到最小的结点，并将其插入到有序区的最后。示例代码如下：

function selectSort (list) {
  let head = list.head;
  if (!head || !head.next) {
    return;
  }
  let firstSorted, lastSorted, minPrev, min, p;
  while (head){
    // 1. 在链表中找到数据域最小的结点
    for (p = head, min = head; p.next; p = p.next) {
      if (p.next.val < min.val) {
        minPrev = p;
        min = p.next;
      }
    }
    // 2. 构建有序链表
    if (!firstSorted) {
      firstSorted = min; // 如果目前还是一个空链表，那么设置 firstSorted
    } else {
      lastSorted.next = min; // 否则直接将min加在有序链表的末端 
    }
    // 3. 调整lastSorted
    lastSorted = min;
    // 4. 将min从原链表中移除
    if (min == head) { // 如果找到的最小结点就是第一个结点
      head = head.next; // 显然，让head指向原head.next（即第二个结点）就可以了
    }  else {
      minPrev.next = min.next; // 移除
    }
  }
  if (lastSorted) {
    lastSorted.next = null; // 清空有序链表的最后结点的next引用
  }
  list.head = firstSorted;
  list.tail = lastSorted;
}


// 4. 快速排序
// 快速排序的核心是partition，我们选取第一个结点作为枢轴，然后把小于枢轴的结点放到一个链中，
// 把不小于枢轴的结点放到另一个链中，最后把两条链以及枢轴连接成一条链。示例代码如下：

function quickSort (list) {
  let head = list.head;
  if (!head || !head.next) {
    return;
  }
  let tempHead = new Node(0);
  tempHead.next = head;
  recursion(tempHead, head, null);
  let h = list.head = tempHead.next;
  while(h){
    list.tail = h;
    h = h.next;
  }
}
function recursion (prevHead, head, tail) {
  // 链表范围是[low, high)
  if (head != tail && head.next != tail) {
    let mid = partition(prevHead, head, tail); // 注意这里head可能不再指向链表头了
    recursion(prevHead, prevHead.next, mid);
    recursion(mid, mid.next, tail);
  }
}
function partition (prevLow, low, high) {
  // 链表范围是(low, high)
  let pivotkey = low.data; // low作为枢轴
  let little = new Node('');
  let bigger = new Node('');
  let littleHead = little; // 保存原来的引用
  let biggerHead = bigger; // 保存原来的引用
  for (let node = low.next; node != high; node = node.next) {
    if (node.data < pivotkey) {
      little.next = node;
      little = node;
    } else {
      bigger.next = node;
      bigger = node;
    }
  }
  // [prevLow litterNode ... low  biggerHead ... big, high]
  bigger.next = high;
  little.next = low;
  low.next = biggerHead.next; // 去掉biggerHead
  prevLow.next = littleHead.next; // 去掉littleHead
  return low;
}
// ======

function quicksort(head){
  if(!head || !head.next){
    return head;
  }
  let prevHead = new LinkNode(0)
  prevHead.next = head;
  quicksort(prevHead, null);
  return prevHead.next;
}

function recursion(start, end){
  if (start.next !== end){
    let [prevPivot, pivot] = partition(start, end);
    recursion(start, prevPivot);
    recursion(pivot, end);
  }
}

function partition(prevHead, end){// start一开始是tempHead, end为null
  let second = prevHead.next.next;// 第二个元素
  let prevPivot = prevHead.next;// 第一个元素
  prevPivot.next = end; // 将第二个元素移出来
  pivot = prevPivot;// prevPivot
  // [prevHead,...,prevPivot, pivot,...,end]
  while( second != end ){
    let next = second.next;
    if (second.val >= prevPivot.val){
      // 如果第二个元素大于第一个元素，第一个元素为prevPivot
      // 那么将它发配到pivot的右侧   
      // pivot -> second->  pivot.next
      second.next = pivot.next;
      pivot.next = second;
      if(second.val == prevPivot.val){
        pivot = pivot.next;
      }
    } else if (second.val < prevPivot.val){
      // 将它发配到prevPivot的左侧，prevHead的右侧
      //  prevHead -> second->  prevHead.next
      second.next = prevHead.next;
      prevHead.next = second;
    } 
    second = next;
  }
  return [prevPivot, pivot];
}




// 3.4　栈
// 你可以将栈看作一个弱化的数组。栈只有两个改变长度的方法：pop与push。
// 数组则有许多改变数组长度的方法：shift、unshift、pop、push、splice，等等。
// 例如，一堆压在一起的书，可以被看作一个栈。

// 3.4.1　栈的特点和相关概念
// 栈有如下特点。
// 栈中的数据元素遵循“先进后出”（first in last out）的原则，简称FILO结构。
// 限定只能在栈顶进行插入和删除操作。
// 栈的相关概念如下。
// 栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。
// 压栈：栈的插入操作，也叫进栈、入栈，方法名通常为push。
// 弹栈：栈的删除操作，也叫出栈，方法名通常为pop。

// 3.4.2　栈相关的方法
// 接着，我们介绍一下栈相关的方法。
// pop：删除操作。
// push：插入元素。
// isEmpty：判断栈是否为空。
// size：返回栈的长度。
// top或peek：取得栈顶元素的值。
// C++中取栈顶元素的方法叫top，而Java中的方法则叫peek。
// 栈的实现很简单，就是把数组“包”一层，限制用户从其他位置操作数组，实现代码如下：


class Stack {
  constructor() {
    this.data = [];
  }
  pop() {
    return this.data.pop();
  }
  push(el) {
    this.data.push(el);
  }
  size() {
    return this.data.length;
  }
  isEmpty() {
    return this.data.length === 0;
  }
  top() {
    return this.data[this.data.length - 1];
  }
  peek(){
     return this.top();
  }
}

let stack = new Stack();
stack.push(3);
stack.push(5);
stack.push(8);
stack.push(9);
console.log(stack.top());
stack.pop();
stack.pop();
console.log(stack.size());



// 3.4.3　栈的应用场景

// 1. 逆序输出
// 栈最大的特点是先进后出，所以逆序输出是栈经常用到的一个应用场景。首先把所有元素依次入栈，然后把所有元素出栈并输出，这样就实现了逆序输出。
// 2. 语法检查，符号成对出现 
// 在我们日常的编程中，括号都是成对出现的，比如“()”“[]”“{}”“<>”这些成对出现的符号。

// 具体处理的方法就是：
// 凡是遇到括号的前半部分，即把这个元素入栈，凡是遇到括号的后半部分就比对栈顶元素是否与该元素相匹配，如果匹配，则前半部分出
// 栈，否则就是匹配出错。最后还要判定栈是否为空，可能只有入栈，没有出栈。括号正确性匹配的示例代码如下所示：
function match(s) {
  let stack = new Stack();
  for (let i = 0; i < s.length; i++) {
    let c = s.charAt(i);
    switch (c) {
      case ')':
        if (stack.pop() == '(') {
          break;
        } else {
          return false;
        }
      case ']':
        if (stack.pop() == '[') {
          break;
        } else {
          return false;
        }
      case '}':
        if (stack.pop() == '{') {
          break;
        } else {
          return false;
        }
      case '(':
      case '[':
      case '{':
        stack.push(c);
        break;
    }
  }
  return stack.isEmpty();
}

console.log(match("{[()]()[{}]}"));
console.log(match("{[()]}"));



// 3. 进制转换
// 十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法有很多，其中一个简单算法基于下列原理：
// N = (N div d)d + N mod d（其中：div为整除运算，mod为求余运算）
// 例如，(2007)10 = (3727)8


// 从低位到高位产生八进制的各个数位，然后从高位到低位进行输出，结果数位的使用具有后出现先使用的特点，
// 因此生成的结果数位可以使用一个栈来存储，然后从栈顶开始依次输出即可得到相应的转换结果。
// 代码实现如下：
// 二进制转换方法
function toBinary(num) {
  let stack = new Stack();
  while (num > 0) {
    stack.push(num % 2);
    num = ~~(num / 2); // 去掉小数
  }
  let ret = "";
  while (!stack.isEmpty()) {
    ret += stack.pop();
  }
  return ret;
}

// 通用进制转换方法
function baseConvert(num, base) {
  let stack = new Stack();
  while (num > 0) {
    stack.push(num % base);
    num = ~~(num / base); // 去掉小数
  }
  let dights = "0123456789abcdef";
  let ret = "";
  while (!stack.isEmpty()) {
    ret += dights[stack.pop()];
  }
  return ret;
}
console.log(baseConvert(2007, 8)); // 3727


// 4. 表达式求值
// 表达式求值是程序设计语言中一个最基本的问题

// 它的实现是栈应用的又一个典型例子。这里介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。
// 要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。例如要对下述表达式求值：

// 首先，要了解算术四则运算的规则。
// 先乘除，后加减。
// 从左算到右。
// 先括号内，后括号外。
// 由此，这个算术表达式的计算顺序应为：

// 任何一个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的。界限符也就是小括号，运算符包括加减乘除，以及更复杂的求余、三角函数等。这里我们只讨论比较简单的算术表达式，只包括加减乘除四种运算符。
// 我们把运算符和界限符统称为算符，根据上述3条运算规则，在运算每一步时，任意两个相继出现的算符θ1和θ2之间的优先关系至多是下面三种关系：
// (1)	θ1 < θ2，θ1的优先级低于θ2；
// (2)	θ1 = θ2，θ1的优先级等于θ2；
// (3)	θ1 > θ2，θ1的优先级大于θ2。 


// 由规则(3)可知，+、、×和÷为θ1时的优先级均低于“(”，但高于右括号“)”。
// 基于上述的论述，首先，我们来讨论如何使用算符优先算法来实现表达式的求值。
// 为了实现该算法，我们需要使用两个工作栈：一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。
// 算法的基本思想如下。
// (1)	设置两个栈：操作数栈（OPND）和运算符栈（OPTR）。
// (2)	依次读入表达式中的每个字符，若是操作数，则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先级后再作相应操作。
// (3)	若该运算符的优先级大于栈顶运算符的优先级，则该运算符直接进OPTR栈；反之若运算符的优先级小于栈顶运算符的优先级，则弹出栈顶运算符，并从OPND栈弹出两个数进行该栈顶运算符的运算，运算结果再加入OPND栈。
// (4)	循环往复地进行第(2)步，直到将该操作符加入OPTR栈。
// (5)	表达式读取结束，若两个栈都不为空，则依次弹出OPTR栈中的运算符和OPND栈中的两个操作数，进行运算后，再将运算结果加入OPND栈。直到OPTR栈为空，OPND栈只剩下一个元素，则该元素就是最后的运算结果。
// (6)	中间若出现差错，比如最后OPND栈剩下不止一个数，则视为表达式出错。
// 下面是完整代码：
function evaluate(expression) {
  let OPND_stack = new Stack(); // 操作数栈
  let OPTR_stack = new Stack(); // 运算符栈
  // 遍历这个表达式
  for (let i = 0; i < expression.length; i++) {
    let c = expression.charAt(i);
    // 如果当前字符是数字，也就是操作数
    if (isDigit(c) || c == '.') {
      let stringBulider = "";
      // 操作数的拼接，包括小数点
      while (i < expression.length && (isDigit(c = expression.charAt(i)) || c == '.')) {
        stringBulider += c;
        i++;
      }
      // 操作数入栈
      OPND_stack.push(Number(stringBulider));
      // 跳过本次循环，i的值已经增加过，所以要减去
      i--;
      continue;
    } else {
      // 当前的字符是运算符
      outer: while (!OPTR_stack.isEmpty()) {
        switch (precede(OPTR_stack.top(), c)) {
          case '<':
            // 栈顶运算符小于该运算符，该运算符直接入栈
            OPTR_stack.push(c);
            break outer;
          case '=':
            // 栈顶运算符等于该运算符，只有一种情况，左右括号匹配，弹出左括号
            OPTR_stack.pop();
            break outer;
          case '>':ß
            // 栈顶运算符大于该运算符
            let operator = OPTR_stack.pop();
            // 如果有多余的运算符却没有操作数可以计算了，那么说明表达式错误
            try {
              let opnd2 = OPND_stack.pop();
              let opnd1 = OPND_stack.pop();
              OPND_stack.push(operate(opnd1, operator, opnd2));
            } catch (e) {
              console.log("表达式有误0！");
              return;
            }
            break;
        }
      }
      // 第一次栈为空的情况，直接入栈。还有退栈直至栈为空的情况，当前运算符也需要入栈
      if (OPTR_stack.isEmpty()) {
        OPTR_stack.push(c);
      }
    }
  }
  while (!OPTR_stack.isEmpty()) {
    let optr = OPTR_stack.pop();
    // 如果有多余的运算符却没有操作数可以计算了，那么说明表达式错误
    try {
      let opnd2 = OPND_stack.pop();
      let opnd1 = OPND_stack.pop();
      OPND_stack.push(operate(opnd1, optr, opnd2));
    } catch (e) {
      console.log("表达式有误！");
      return;
    }
  }
  if (OPND_stack.size() == 1) {
    return OPND_stack.pop();
  } else {
    console.log("表达式有误！");
    return;
  }
  return 0;
}

function isDigit(c) {
  return /[0-9]/.test(c);
}

function operate(opnd1, optr, opnd2) { // 运算
  switch (optr) {
    case '+':
      return opnd1 + opnd2;
    case '-':
      return opnd1 - opnd2;
    case '*':
      return opnd1 * opnd2;
    case '/':
      return opnd1 / opnd2;
  }
  return 0;
}
// 比较两个运算符的优先级大小
function precede(θ1, θ2) {
  if (θ1 == '+' || θ1 == '-') {
    if (θ2 == '+' || θ2 == '-' || θ2 == ')') {
      return '>';
    } else {
      return '<';
    }
  } else if (θ1 == '*' || θ1 == '/') {
    if (θ2 == '(') {
      return '<';
    } else {
      return '>';
    }
  } else if (θ1 == '(') {
    if (θ2 == ')') {
      return '=';
    } else {
      return '<';
    }
  } else if (θ1 == ')') {
    return '>';
  }
  return '>';
}
console.log(evaluate("12*(3+4)-6+8/1"));




// 3.5　队列
// 队列（queue）也是一种非常简单的数据结构，栈是先进后出，它是先进先出（FIFO，first in first out）。
// 队列在现实生活中很常见，例如可以用来模拟人们在银行里排队，打印机打印文件，飞机等待起飞，互联网上数据包的发送等。
// 和栈一样，队列是一种操作受限制的线性表。进行插入操作的一端称为队尾，进行删除操作的一端称为队头。

// 3.5.1　队列的常用方法
// 队列的常用方法如下。
// size：求长度。
// isEmpty：判断是否为空。
// queue/add：入队。
// dequeue/remove：出队。
// peek：访问第一个元素。
// 队列常用方法的示例代码如下所示：
class Queue {
  constructor() {
    this.data = [];
  }
  queue(el) {
    return this.data.push(el);
  }
  dequeue() {
    this.data.shift();
  }
  size() {
    return this.data.length;
  }
  isEmpty() {
    return this.data.length === 0;
  }
  peek() {
    return this.data[0];
  }
}
或
class Queue {
  constructor() {
    this.data = [];
    this.front = 0;// 头指针
    this.rear = 0;// 末指针
  }
  queue(el) {
    this.rear++;
    return this.data[this.rear] = el;
  }
  dequeue() {
    if (this.rear > 0) {
      this.rear--;
      this.data.length = this.rear;
    }
  }
  size() {
    return this.rear;
  }
  isEmpty() {
    return this.front == this.rear;
  }
  peek() {
    return this.data[1];
  }
}


// 3.5.2　队列的典型应用
// 队列的最典型应用就是求解迷宫问题。迷宫问题是指给定一个M×N的迷宫、入口与出口、行走规则，求一条从指定入口到出口的路径。

// 所求路径必须是简单路径，即路径不重复。
// 迷宫问题可以用栈或者队列来求解，其中使用队列求解出的路径是最短路径。
// 这其实已经涉及了比较往后的知识点——图的广度优先遍历（缩写为BFS）。
// 有关队列及迷宫问题的更精准的解释，可以自行查询。

// 3.6　散列简述
// 散列又叫哈希（hash），是把任意长度的输入（又叫预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。它其实是我们前端人最常用的数据结构了，因为JavaScript对象就是一个散列。在实现链表时，我们使用insertAt来指定数据放入某个位置上。但这个需要遍历内部的结构，即便使用了双向链表，其查找速度还是无法与数组相比拟。然而数组也有其不足之处，它查找容易，插入和删除困难；链表则查找困难，插入和删除容易。
// 基于以上这几点原因，前辈们通过某种算法将关键字转换成数字，实现了O(1)的插入、删除与查找，综合了以上两者的优点，这就是散列。
// 散列法存储的线性表称为散列表，使用的函数称为散列函数，所得的存储位置称为散列地址。通常情况下，散列表的存储空间是一个一维数组，而其散列地址为数组的下标。散列表中的一个位置称为槽（slot）。关于散列的内容，我们会在第4章中详细介绍。
// 3.7　位图
// 笔者一直纠结是不是将它放在排序的章节中，计数排序就是通过位图操作进行排序的。位图其实是一串二进制数字。显然，二进制是99％的前端人的盲区，因为二进制涉及位操作，很少有人掌握这部分知识。因此，我们需要对位操作进行再封装。
// 3.7.1　位图简述
// 讲这个之前，大家回忆一下计数排序，它用了一个庞大的数组来装载数据，并假装将数据放入与它的值相同的位置上。假设数据量非常庞大，达到数十亿，这时计算机的内存能放得下吗？为了解决这个问题，科学家想到了用二进制数来代替数组，如果这个位数上有与其值相等的元素，就将该位数设置为1，否则就设置为0。
// 数组[1,2,5,4,7]可以用位图表示为 10110110，因为数组中的最大值是7，所以要建立一个长度为8位的二进制，让其对应的位置变成1，这样内存的占用就会大大减少。
// 我们再来看一下JavaScript如何表示二进制。
// 0b11100就是一个二进制数，表示28，要求前面两位是0b。在创建时，我们可以先创建一个字符串，再不断往前加数字，然后前面加上0b，最终进入Number构造器中，即Number("0b111000")。
// 我们再看如何操作位数。比如，我们将某一位变成1或0，此时虽然可以使用split方法将其转换成数组，再对其改动，然后再使用join函数处理。但这不是算法题允许的操作方式。算法尊重的是简洁性与普适性，而不是各种语言的特殊性。如果大家在大学没有学过位操作，也没关系，数据结构就是将这些极底层的东西封装一下。下面放出将某一位变成1与0的两个方法。
// 将某一位变成1的方法：
function change1(num, digit) {
  // digit 位数是从个位起，个位是0，十位是1，百位是2
  let old = num;
  let mask = 1 << digit;
  num = num | mask;
  console.log(old.toString(2),"改变第"+digit+"位为1得到", num.toString(2));
  return num;
}
change1(Number("0b00010"), 0);

// 将某一位变成0的方法：

function change0(num, digit) {// digit从0开始
  let old = num;
  let mask = 1 << digit;
  num = num & (~mask);
  console.log(old.toString(2),"改变第"+digit+"位为0得到", num.toString(2));
  return num;
}
change0(Number("0b1111"), 2);

// 最后，我们来看如何遍历位数，得知某一位是0还是1，通过判定这个可以将它转换为字符串，然后通过charAt函数对其进行操作，但这也太慢。
// 获得二进制数中某一位的值的代码如下：

function getBit(num, digit) {
  let ret = (num >> digit) & 1;
  console.log(num.toString(2),"的第"+digit+"位的值是", ret);
  return ret;
}
getBit(Number("0b10111"), 0);
getBit(Number("0b10111"), 1);
getBit(Number("0b10111"), 2);
getBit(Number("0b10111"), 3);
getBit(Number("0b10111"), 4);
getBit(Number("0b10110"), 0);
既然知道如何创建二进制及以上3个方法了，我们就可以编写位图类了。
位图类的实现代码如下：
class BitMap {
  constructor(array) {// 传入一个非负整数数组
    let num = this.banariy = 0;
    for (let i = 0; i < array.length; i++) {
      num = this.change1(num, array[i]); // 将相应的位变成1
    }
    this.banariy = el;
  }
  change0(num, digit) {// 将某一位变成0
    let mask = 1 << digit;
    return num & (~mask);
  }
  change1(num, digit) {// 将某一位变成1
    let mask = 1 << digit;
    return = num | mask;
  }
  get(digit) {// 得到某一位的值，也可以判定digit在不在原数组
    return (this.banariy >> digit) & 1;
  }
  toArray() {// 返回一个排好序的整数数组
    let num = this.banariy;
    let n = num.toString(2).length;
    let ret = [];
    for (let i = 0; i < n; i++) {
      if ((num >> digit) & 1) {
        ret.push(num);
      }
    }
    return ret;
  }
}
理论上来说，这样写是对的，但这不适合JavaScript，JavaScript能够表示的整数范围是正负数的绝对值都不能大于，也就是正负数的绝对值都不能大于9 007 199 254 740 992。这个数是16位的，超过16位的整数JavaScript就不能精确表示了。
既然不能用一个超长的二进制数来表示数组，那么我们可以用一个长度为16的数字数组表示原有数据。修改后的代码如下：
class BitMap {
  constructor(array) {// 传入一个非负整数数组
    let boxes = this.bits = [];
    for (let i = 0; i < array.length; i++) {
      let el = array[i];
      let box = Math.floor(el / 16);
      let index = el % 16;
      let bit = boxes[box];// 分析装到哪一个箱中
      if (bit == null) {
        bit = 0;
      }
      // 将相应的位变成1
      boxes[box] = this.change1(bit, index);
    }
  }
  change0(num, digit) {// 将某一位变成0
    let mask = 1 << digit;
    return num & (~mask);
  }
  change1(num, digit) {// 将某一位变成1
    let mask = 1 << digit;
    return num | mask;
  }
  get(digit) {// 判定数字digit是否在原数组
    let box = Math.floor(digit / 16);
    let index = digit % 16;
    let bit = this.bits[box];
    return bit == 0 ? 0 : ((bit >> index) & 1);
  }
  toArray() {// 返回一个排好序的整数数组
    let boxes = this.bits;
    let ret = [];
    for (let i = 0; i < boxes.length; i++) {
      let bit = boxes[i];
      if (bit != 0) {
        for (let j = 0; j < 16; j++) {
          if ((bit >> j) & 1) {
            ret.push(i * 16 + j);
          }
        }
      }
    }
    return ret;
  }
}
位图的构造器也可以使用change1来构建二进制数。
3.7.2　位图的应用
位图适合用于海量数据且不重复的数字数组的查找与排序。下面我们看一些题目。
1. 查找丢失的数
有一组数字，从1到n（此例子假设n=10），无序且不重复。例如：[8,9,2,3,6,1,4,5,7,10]。从中任意删除3个数，顺序也再次被打乱，将这些剩余数字放在一个长度为n3的数组里，请找出其中丢失的数字，要求算法速度需要相对较快。相关代码如下：
function missingNumber1(nums, a,b){
  let bitmap = new BitMap(nums);
  let lost = [];
  for(let i = a; i < b; i++){// 总共10个
    if(bitmap.get(i) == 0){
      lost.push(i);
    }
  }
  return lost;
}
let r = missingNumber1([5,1,6,3,7,8,10], 1, 11);
console.log(r);
/**
let r = missingNumber1([44, 26, 34, 25, 23, 42, 0, 43, 38, 14, 47, 19, 49, 6, 16, 41, 24, 35, 10, 4, 32, 5, 8, 15, 31, 3, 46, 22, 2, 30, 28, 37, 1, 21, 39, 45, 9, 48, 36, 17, 7, 27, 18, 29, 13, 40, 11, 20, 12], 0, 50);
cosnole.log(r);
*/
// 或者
function missingNumber2 (nums, a, b) {
  let str = [];
  nums.forEach(function (el) {
    str[el] = 1;
  });
  for (let i = a; i < b; i++) {
    if (str[i] == null) {
      console.log(i);
      return i;
    }
  }
  return null;
}
// 如果只丢失一个数，可以直接相减，代码如下：
function missingNumber( nums) {
  if (nums.length == 0) return 0;
  let sum = 0;
  for (vaar i=0; i<nums.length; i++) sum+=nums[i];
  return (1+nums.length)*nums.length/2 - sum; 
}



// 2. 判定数字是否存在
// 给出40亿个不重复的unsigned int的整数，没排过序，然后再随机给出一个数，如何快速判断这个数是否在那40亿个数当中？ 
// 这个也简单，调用一下get方法，代码如下：
let bitmap = new BitMap(igNumbers);
console.log(!!bitmap.get(num));


// 3. 海量数据排序问题
// 文件包含1000万（10的7次方）条电话号码记录，每条记录都是7位整数，没有重复的整数。
// 要求对文件进行排序，注意大约只有1MB的内存空间可用，但有充足的磁盘存储空间可用。
// 请设计一个高效的算法。
// 同上，就是调一下BitMap.toArray方法。
// 如果这些数据中有负数或者你不想从0开始遍历呢，比如上题想从10 000 000开始，这个也简单，
// 大家可以翻看计数排序.




// 3.8　块状链表

// 3.8.1　简介
// 块状链表是一种兼容数组与链表优点的结构（本书中上次被这样形容的是散列，但散列在处理冲突时确实让人很头痛）。
// 块状链表的卖点是，各种操作的时间复杂度均为O(sqrt(n))。为了实现这一点，它实际上是将一个数组拆成多个子数组，
// 然后通过next属性将所有子结点连接在一起。普通的链表是将一个个对象连在一起，
// 但一个对象里面只能装一个数据，会造成空间上的浪费，而块状链表的子数组则可以装多个
// ，至于装多少，我们需要一个算法来推算出一个合理的值。这个也不用我们劳神了，科学家们已经给出了现成的答案。
// 假设数组的长度是n，要让它转变为块状链表，那么块状链表的每个子数组（又称为块）的长度应该为[sqrt(n)/2, 2*sqrt(n)]。


// 块状链表与位图差不多，都是一边插入一边排序，插完就已经排好序了。
// 这听起来像插入排序，但插入排序是有后挪过程的，数组越大，向后挪动的次数就越多，这是导致性能低下的原因。
// 我们在插入过程中添加分裂操作，让大数组变成两个数组、三个数组，最后均匀地将每个子数组变成[Math.sqrt(n)/2, 2*Math.sqrt(n)]的长度。
// 以后查找元素也会很快，因为我们选择访问每个块的第一个元素与最后一个元素，如果发现不在这个范围里，就跳到下一个块。
// 删除元素也不会影响到后面的所有元素，只需要进行个别元素的挪动即可。并且配合合并操作，合并相邻的长度过短的块，还能防止碎片化。
// 下面是块状链表的方法属性。
// length：记录总元素个数，内部使用。
// list：第一个子数组（块）。
// insert(el)：插入一个元素，内部会自然分配它到适合的块与位置上。
// remove(el)：移除一个元素。
// forEach(cb)：遍历所有元素，类似数组的所有方法。
// size：返回length。


// 3.8.2　操作
// 1. 插入操作
// 块状链表的插入操作是难点。当我们插入第一个元素时，块状链表的list是不存在的，这时立即创建一个数组，将元素放进去，
// 修正length为1，这就完成了第一次插入操作。当我们插入第二个元素时，我们需要判定其当前块的长度是否允许继续放入元素。
// Math.sqrt(2) 为1.4142，我们在上面说了，Math.sqrt(2) /2至Math.sqrt(2)*2的数组长度都是有效的
// ，但程序不能模糊，我们需要精确的数字，那我们就用Math.sqrt(2)+1作为当前块的长度。
// 于是第二个数可以放进第一个块中，放进去时可以选择将原数组分裂成2个，
// 再将元素放到前面的数组的末端；也可以选择放入后先进行排序，视情况再分裂。
// 显然，后一种方法简单些。


// 插入操作的代码如下所示：
insert(el, list) {
  if (!list) {
    list = this.list;
  }
  // 情况1，从无到有
  if (!list) {
    this.list = [el];
    this.length = 1;
  } else {
    // 情况2，这元素恰好在这块的范围内，那么先插入再考虑分裂
    let max = Math.sqrt(this.length) + 1;
    if (el < list[list.length - 1]) {
      // ============开始插入排序========
      let m = 0;
      for (let i = 0, n = list.length; i < n; i++) {
        if (el < list[i]) {
          m = i;
          break;
        }
      }
      for (i = list.length - 1; i >= m; i--) {
        list[i + 1] = list[i];
      }
      list[m] = el;
      // ============结束插入排序========
      this.length++;
      if (list.length >= max && list.length > 3) {
        this.split(list);
      }
    } else {
      // 情况3，不在当前块的范围，这时又分两种情况
      // 3.1 这是最后一个块并且块的个数不足
      // 3.2 这是中间的块
      let beyondLengthLimit = list.length < max;
      if (beyondLengthLimit && !list.next) {
        list[list.length] = el;
        this.length++;
        if (list.length >= max && list.length > 3) {
          this.split(list);
        }
      } else {
        this.insert(el, list.next || (list.next = []));
      }
    }
  }
}
// 上面我们用了递归，显然这么多块要处理，要执行相同的操作，最好使用递归实现。接下来的remove、forEach也是这样实现的。


// 2. 分裂操作
// 再看分裂是如何实现的，它是从中间开始遍历，把元素复制到新数组，最后用next将新数组连接起来。
// 分裂操作的代码如下：
split(list) {
  let next = list.next;
  let n = list.length;
  let half = n >> 1;
  let newList = [];
  for (let i = half; i < n; i++) {
    newList[i] = list[i];
  }
  list.length = half;// 缩小原数组的长度
  list.next = newList;
  newList.next = next;// 结点连接后面的块
}


// 3. 移除操作
// 移除操作其实如果不按算法的要求，直接用JavaScript原生方法很容易实现：先用indexOf查找，然后用splice移除。
// 这个在“起稿子”时可以先这样写，然后慢慢换回去。splice移除其实就是后面的元素覆盖前一个元素，最后长度减1
// 。删除后，我们要记得判定长度，看它是否适合做合并操作。
// 移除操作的代码如下所示：
remove(el, list) {
  if (!list) {
    if (!this.list) {
      return false;// 返回false说明没有真正地执行移除操作
    }
    list = this.list;
  }
  if (el <= list[list.length - 1]) {
    let hasRemove = false;
    for (let i = 0, n = list.length; i < n; i++) {
      let elem = list[i];
      if (elem === el) { // 后面的覆盖前面的
        list[i] = list[i + 1];
        hasRemove = true;
        break;
      }
    }
    if (hasRemove) {
      for (; i < n; i++) {
        list[i] = list[i + 1];
      }
      this.length--; // 减少块的长度
      list.length--; // 减少总长度
      let max = Math.sqrt(this.length) / 2;
      if (list.length < max && list.next) {
        this.merge(list, list.next);
      }
      return true;// 真的删除目标元素，每次只删除一个
    }
  } else {
    let next = list.next;
    if (next) {
      return this.remove(el, next);
    }
  }
}


// 4. 合并操作
// 合并操作就不详述了，下面给出完整代码：
class BlockList {
  constructor() {
    this.length = 0;
    this.list = null;
  }
  size() {
    return this.length;
  }
  split(list) {/**略**/ }
  merge(list, next) {
    let n = list.length;
    let m = next.length;
    for (let i = 0; i < m; i++) {
      list[n + i] = next[i];
    }
    list.next = next.next;
  }
  insert(, list){/**略**/ }
  remove(el, list){/**略**/ }
  forEach(cb, list, index) {
    list = list || this.list;
    index = index || 0;
    if (!list) {
      return;
    }
    for (let i = 0; i < list.length; i++) {
      cb(list[i], index);
      index++;
    }
    if (list.next) {
      this.forEach(cb, list.next, index);
    }
  }
}
let array = [2, 3, 7, 1, 8, 7, 9, 6, 0, 10];
let list = new BlockList;
array.forEach(function(el) {
  list.insert(el);
});
console.log(list);
list.remove(7);